import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
public class ExprExercise {
    private final static ArrayList<Character> cArr = new ArrayList<Character>();
    private final static ArrayList<Integer> dArr = new ArrayList<Integer>();
    private static int index = 0;

    private static int get_index(char theta) {
        switch (theta) {
            case '+':
                index = 0;
                break;
            case '-':
                index = 1;
                break;
            case '*':
                index = 2;
                break;
            case '/':
                index = 3;
                break;
            case '(':
                index = 4;
                break;
            case ')':
                index = 5;
                break;
            case '=':
                index = 6;
            default:
                break;
        }
        return index;
    }

    private static char get_priority(char theta1, char theta2) {
        char[][] priority = {
                {'>', '>', '<', '<', '<', '>', '>'},
                {'>', '>', '<', '<', '<', '>', '>'},
                {'>', '>', '>', '>', '<', '>', '>'},
                {'>', '>', '>', '>', '<', '>', '>'},
                {'<', '<', '<', '<', '<', '=', '0'},
                {'>', '>', '>', '>', '0', '>', '>'},
                {'<', '<', '<', '<', '<', '0', '='},
        };

        int index1 = get_index(theta1);
        int index2 = get_index(theta2);
        return priority[index1][index2];
    }

    private static int calculate(int b, char theta, int a) {
        switch (theta) {
            case '+':
                return b + a;
            case '-':
                return b - a;
            case '*':
                return b * a;
            case '/':
                return b / a;
            default:
                break;
        }
        return 0;
    }

    private static int expr(String s) {
        cArr.add('=');
        int counter = 0;
        char[] c = s.toCharArray();
        int loc = 0;
        //int i = 1;
        while (c[loc] != '=' || !cArr.get(cArr.size() - 1).equals('='))   
        {
            if (Character.isDigit(c[loc]))   
            {
                if (counter == 1)   
                {
                    int t = dArr.get(dArr.size() - 1);
                    dArr.remove(dArr.size() - 1);
                    dArr.add(t * 10 + (c[loc] - '0'));
                } else {
                    dArr.add((int) (c[loc] - '0'));
                    counter++;
                }
                loc++;
            } else{
                counter = 0;
                switch (get_priority(cArr.get(cArr.size() - 1), c[loc]))
                {
                    case '<':
                        cArr.add(c[loc]);
                        loc++;
                        break;
                    case '=':
                        cArr.remove(cArr.size() - 1);
                        loc++;
                        break;
                    case '>':
                        char theta = cArr.get(cArr.size() - 1);
                        cArr.remove(cArr.size() - 1);
                        int a = dArr.get(dArr.size() - 1);
                        dArr.remove(dArr.size() - 1);
                        int b = dArr.get(dArr.size() - 1);
                        dArr.remove(dArr.size() - 1);
                        dArr.add(calculate(b, theta, a));
                }
            }
        }
        return dArr.get(dArr.size() - 1);   
    }
	
	public static void main(String[] args){
		String test1 = "1+2=";
		System.out.println(test1 + "\n" + "result : " + expr(test1));
		String test2 = "3-(2+1)=";
		System.out.println("\n" + test2 + "\n" + "result : " + expr(test2));
		String test3 = "4-(3-1)=";
		System.out.println("\n" + test3 + "\n" + "result : " + expr(test3));
		String test4 = "1+2*3=";
		System.out.println("\n" + test4 + "\n" + "result : " + expr(test4));
		String test5 = "4/2*2=";
		System.out.println("\n" + test5 + "\n" + "result : " + expr(test5));
		String test6 = "(1+2)*2+3=";
		System.out.println("\n" + test6 + "\n" + "result : " + expr(test6));
    }
}
